#include <iostream>

using namespace std;

/*
Problem description: 

Assume that you are assigning continuous section of board to each painter such that its total length must 
not exceed a predefined maximum, costmax. 
Then, you are able to find the number of painters that is required, x. Following are some key observations:
http://www.leetcode.com/2011/04/the-painters-partition-problem-part-ii.html
 
 1.The lowest possible value for costmax must be the maximum element in A (name this as lo).
 2.The highest possible value for costmax must be the entire sum of A, (name this as hi).
 3.As costmax increases, x decreases. The opposite also holds true.

 
Now, the question translates directly into:
 
How do we use binary search to find the minimum of costmax while satisfying the condition x = k? 
The search space will be the range of [lo, hi].

*/

int getMax(int A[], int n) 
{
    int max = INT_MIN; 
    for (int i = 0; i < n; i++) 
    {
        if (A[i] > max) 
            max = A[i];  
    }
    
    return max;
}

int getSum(int A[], int n) 
{ 
    int total = 0;  
    for (int i = 0; i < n; i++) 
        total += A[i];  
    return total;
}

// I do not quite understand this part, but check in for now
// need to think this over
int getRequiredPainters(int A[], int n, int maxLengthPerPainter) 
{
    int total = 0, numPainters = 1;
    
    for (int i = 0; i < n; i++) 
    {
        total += A[i];  
        if (total > maxLengthPerPainter) 
        {
            total = A[i];   
            numPainters++;    
        }
    }
    
    return numPainters;
}

int partition_BinarySearch(int A[], int n, int k) 
{
    int lo = getMax(A, n);  
    int hi = getSum(A, n); 
    
    while (lo < hi) 
    {
        int mid = lo + (hi-lo)/2;    
        int requiredPainters = getRequiredPainters(A, n, mid);   
        
        if (requiredPainters <= k)    
            hi = mid;  
        else
            lo = mid+1;  
    }
    
    return lo;
}